package puzzle.projecteuler.p200;

import astudy.util.AdvMath;

public class Problem101C {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();
		long[] u = new long[10];
		for (int n = 1; n <= 10; n ++) {
			u[n-1] = u(n);
		}
		long sum = 0;
		for (int k = 1; k <= 10; k ++) {
			sum += BOP(u, k);
		}
		System.out.println("sum = " + sum);
		System.out.println((System.currentTimeMillis() - s) + " ms");
	}

	/**
	 * 根据u的前k项，作为k-1阶等差数列，求第n项的值
	 * v = C(k,1)*u_k - C(k,2)*u_(k-1) + ... + (-1)^(i-1)*C(k,i)*u_(k+1-i) + ... + (-1)^(k-1)*C(k,k)*u_1 
	 * @param u
	 * @param k
	 * @param n
	 */
	public static long OP(long[] u, int k, int n) {

		if (n <= k) {
			return u[n-1];
		} else {
			long v = 0;
			for (int i = 1; i <= k; i ++) {
				v += (((i-1)%2 == 0)?1:-1) * AdvMath.C(k, i) * u[k-i];
			}
			return v;
		}
	}
	
	public static long BOP(long[] u, int k) {
		return OP(u, k, k+1);
	}
	
	/**
	 * un = 1 - n + n^2 - n^3 + n^4 - n^5 + n^6 - n^7 + n^8 - n^9 + n^10
	 *    = (n^11+1)(n+1)
	 */
	public static long u(int n) {
		return ((long)Math.pow(n, 11)+1)/(long)(n+1);
	}
}
